#include "GRASP.h"
#include "Lista.h"

SolucaoGRASPSTS *GRASP::construcao(){
	SolucaoGRASPSTS *sol = new SolucaoGRASPSTS(this->tamSolucao);
	sol->init();
	//Inicializa a funcao gulosa adaptativa
	Solucao::initGulosa();
	
	while(!sol->todosClientesAlocados()){
		Lista candidatos;
		//Inicializando a lista de candidatos
		for(int i = 0; i < sol->tamanho; i++){
			if(sol->solucao[i] != true)
				candidatos.insereOrdenado(i, sol->g(i));
		}
		//Setando o valor de filtro dos elementos do LCR
		double gmin = candidatos.inicio->gulosa;
		//double gmin = candidatos.getPos(0)->gulosa;
		double gmax = candidatos.final->gulosa;
		//double gmax = candidatos.getPos(candidatos.tamanho() - 1)->gulosa;
		//printf("MIN: %f - MAX: %f\n", gmin, gmax);
		double filtro = gmin + this->alpha*(gmax - gmin);
		//Inicializando o LCR
		Lista LCR;
		for(int i = 0; i < candidatos.tamanho(); i++){
			NoLista *aux = candidatos.getPos(i);
			if(aux->gulosa <= filtro){
				LCR.insere(aux->elemento);
				//delete aux;
			}else{
				//delete aux;
				break;
			}
		}
		//Escolha aleatoria do elemento na LCR
		NoLista *aux = LCR.getRandom();
		//printf("Pos: %d\n", aux->elemento);
		//Seta o elemento da solucao em sol
		sol->setElemento(aux->elemento);
		//printf("Construcao Parcial: %s\n", sol->print());
		//Remove o elemento da lista candidatos
		candidatos.remove(aux->elemento);
		//delete aux;
	}
	//printf("Construcao: %s\n", sol->print()); 
	sol->f();
	return sol;
}

SolucaoGRASPSTS *GRASP::buscaLocal(SolucaoGRASPSTS *solAtual){
 	//Criando os vizinhos da solucao atual
	SolucaoGRASPSTS *sol = NULL;
        //Operador ADD
        SolucaoGRASPSTS *soladd = solAtual->getVizinhosADD();
        
	//Operador DROP
        SolucaoGRASPSTS *soldrop = solAtual->getVizinhosDROP();

        //Operador SWAP
	SolucaoGRASPSTS *solswap = solAtual->getVizinhosSWAP();

	//Procura a melhor solucao apos os tres operadores
        if((soladd != NULL)&&(soldrop != NULL)&&(solswap != NULL)){
                if(soladd->avaliacao <= soldrop->avaliacao){
                        delete soldrop;
                        sol = soladd;
                }else{
                        delete soladd;
                        sol = soldrop;
                }
                if(solswap->avaliacao < sol->avaliacao){
                        delete sol;
                        sol = solswap;
                }else{
                        delete solswap;
                }
        }else{
                if(soladd == NULL){
                        if(soldrop != NULL){
                                sol = soldrop;
                        }
                }else{
                  if(soldrop == NULL){
                                sol = soladd;
                        }else{
                                if(soladd->avaliacao >= soldrop->avaliacao){
                                        delete soldrop;
                                        sol = soladd;
                                }else{
                                        delete soladd;
                                        sol = soldrop;
                                }

                        }
                }
                if(sol != NULL){
                        if(solswap != NULL){
                                if(solswap->avaliacao < sol->avaliacao){
                                        delete sol;
                                        sol = solswap;
                                }else{
                                        delete solswap;
                                }
                        }
                }else{
                	sol = solswap;
                }
        }
        return sol;
}

SolucaoGRASPSTS *GRASP::descida(SolucaoGRASPSTS *sbl){
	SolucaoGRASPSTS *sol = new SolucaoGRASPSTS(sbl);
	SolucaoGRASPSTS *sbest = new SolucaoGRASPSTS(sbl);
	double fant = 0;
	do{
		fant = sol->avaliacao;
		SolucaoGRASPSTS *sblAux = sol;
		//delete svns;
		sol = this->buscaLocal(sblAux);
		if(sol != NULL){
			delete sblAux;
			if(sol->avaliacao < sbest->avaliacao){
				delete sbest;
				sbest = new SolucaoGRASPSTS(sol);
			}
		}else
			delete sblAux;
	}while(sol->avaliacao < fant);
	return sbest;
}

SolucaoGRASPSTS *GRASP::ILS(SolucaoGRASPSTS *sbl){
	SolucaoGRASPSTS *svns = new SolucaoGRASPSTS(sbl);
	SolucaoGRASPSTS *sbest = new SolucaoGRASPSTS(sbl);
	int n = Solucao::tamanho/4;
	
	for(int i=0; i<n; i++){
		int shake = rand()%4 + 2;
		for(int j=0; j<shake; j++){
			SolucaoGRASPSTS *svnsAux = svns->getVizinho(rand()%Solucao::tamanho);
			delete svns;
			svns = svnsAux;
		}
		SolucaoGRASPSTS *sblAux = svns;//->getSWAP(rand()%Solucao::tamanho, rand()%Solucao::tamanho);
		//delete svns;
		svns = this->buscaLocal(sblAux);
		if(svns != NULL){
			delete sblAux;
			if(svns->avaliacao < sbest->avaliacao){
				delete sbest;
				sbest = new SolucaoGRASPSTS(svns);
			}
		}else
			delete sblAux;
	}
	return sbest;
}

#define FILTRO 1

void GRASP::start(int GRASPmax){
	gettimeofday(&tempoAntes, NULL);
	srand(time(NULL));
	double finicial = 100000000;
	SolucaoGRASPSTS *sol;
	for(int iter = 0; iter < GRASPmax; iter++){
		double fConstrInicial = 1000000000;
		//sol = this->construcao();
		sol = NULL;
		for(int i=0; i<FILTRO; i++){
			SolucaoGRASPSTS *sconstr = this->construcao();
			if(sconstr->avaliacao < fConstrInicial){
				if(sol != NULL)
					delete sol;
				sol = sconstr;
				fConstrInicial = sconstr->avaliacao;
			}else
				delete sconstr;
		}
		//printf("Parcial: %s\n", sol->print());
		SolucaoGRASPSTS *sbl = this->buscaLocal(sol);
		//printf("Parcial: %s\n", sbl->print());
		
		SolucaoGRASPSTS *svns = this->ILS(sbl);
		/*SolucaoGRASPSTS *sbest = new SolucaoGRASPSTS(sbl);
		sbl = NULL;
		int n = Solucao::tamanho/4;
//puts("HERE0.0");
		for(int i=0; i<n; i++){
			int shake = rand()%4 + 2;
			for(int j=0; j<shake; j++){
				SolucaoGRASPSTS *svnsAux = svns->getVizinho(rand()%Solucao::tamanho);
				delete svns;
				svns = svnsAux;
			}
			SolucaoGRASPSTS *sblAux = svns;//->getSWAP(rand()%Solucao::tamanho, rand()%Solucao::tamanho);
			//delete svns;
			svns = this->buscaLocal(sblAux);
			delete sblAux;
			if(svns->avaliacao < sbest->avaliacao){
				delete sbest;
				sbest = new SolucaoGRASPSTS(svns);
			}
		}*/
//puts("HERE0");
		if(sol != NULL)
			delete sol;
		if(svns->avaliacao < finicial){
			if(this->s != NULL)
				delete this->s;
			this->s = svns;
			finicial = svns->avaliacao;
			melhorIter = iter;
		}	
	}
	gettimeofday(&tempoDepois, NULL);
}


